{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Time to Build Blocks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minBuildTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #建造街区的最短时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你是个城市规划工作者，手里负责管辖一系列的街区。在这个街区列表中&nbsp;<code>blocks[i] = t</code>&nbsp;意味着第 &nbsp;<code>i</code>&nbsp;个街区需要&nbsp;<code>t</code>&nbsp;个单位的时间来建造。</p>\n",
    "\n",
    "<p>由于一个街区只能由一个工人来完成建造。</p>\n",
    "\n",
    "<p>所以，一个工人要么需要再召唤一个工人（工人数增加 1）；要么建造完一个街区后回家。这两个决定都需要花费一定的时间。</p>\n",
    "\n",
    "<p>一个工人再召唤一个工人所花费的时间由整数&nbsp;<code>split</code>&nbsp;给出。</p>\n",
    "\n",
    "<p>注意：如果两个工人同时召唤别的工人，那么他们的行为是并行的，所以时间花费仍然是&nbsp;<code>split</code>。</p>\n",
    "\n",
    "<p>最开始的时候只有&nbsp;<strong>一个&nbsp;</strong>工人，请你最后输出建造完所有街区所需要的最少时间。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>blocks = [1], split = 1\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>我们使用 1 个工人在 1 个时间单位内来建完 1 个街区。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>blocks = [1,2], split = 5\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>我们用 5 个时间单位将这个工人分裂为 2 个工人，然后指派每个工人分别去建造街区，从而时间花费为 5 + max(1, 2) = 7\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>blocks = [1,2,3], split = 1\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：\n",
    "</strong>将 1 个工人分裂为 2 个工人，然后指派第一个工人去建造最后一个街区，并将第二个工人分裂为 2 个工人。\n",
    "然后，用这两个未分派的工人分别去建造前两个街区。\n",
    "时间花费为 1 + max(3, 1 + max(1, 2)) = 4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>1 &lt;= blocks.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= blocks[i] &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= split &lt;= 100</code></li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-time-to-build-blocks](https://leetcode.cn/problems/minimum-time-to-build-blocks/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-time-to-build-blocks](https://leetcode.cn/problems/minimum-time-to-build-blocks/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1]\\n1', '[1,2]\\n5', '[1,2,3]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBuildTime(self, blocks: List[int], split: int) -> int:        \n",
    "        # Prepare Heap of Building Time\n",
    "        heapq.heapify(blocks)\n",
    "        \n",
    "        # Make sibling blocks until we are left with only one root node\n",
    "        while len(blocks) > 1:            \n",
    "            # Pop two minimum. The time of the abstracted sub-root will be \n",
    "            # split + max(x, y) which is split + y\n",
    "            x = heapq.heappop(blocks)\n",
    "            y = heapq.heappop(blocks)\n",
    "            heapq.heappush(blocks, split + y)\n",
    "        \n",
    "        # Time of final root node\n",
    "        return heapq.heappop(blocks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minBuildTime(self, blocks: List[int], split: int) -> int:\n",
    "       \n",
    "\n",
    "        heapq.heapify(blocks)\n",
    "        while len(blocks) > 1:\n",
    "            a, b = heapq.heappop(blocks), heapq.heappop(blocks)\n",
    "            heapq.heappush(blocks, split+max(a, b))\n",
    "        return blocks[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBuildTime(self, blocks: List[int], split: int) -> int:\n",
    "        q=[]\n",
    "        for b in blocks:\n",
    "            heapq.heappush(q,b)\n",
    "        while len(q)>1:\n",
    "            x,y=heapq.heappop(q),heapq.heappop(q)\n",
    "            heapq.heappush(q,max(x,y)+split)\n",
    "        return q[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBuildTime(self, blocks: List[int], split: int) -> int:\n",
    "        heapq.heapify(blocks)\n",
    "        while len(blocks) > 1:\n",
    "            a = heapq.heappop(blocks)\n",
    "            b = heapq.heappop(blocks)\n",
    "            heapq.heappush(blocks, split + max(a, b))\n",
    "        return blocks[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBuildTime(self, pq: List[int], split: int) -> int:\n",
    "        heapify(pq)\n",
    "        while len(pq)>1:\n",
    "            heappop(pq)\n",
    "            heappushpop(pq,pq[0]+split)\n",
    "        return pq[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBuildTime(self, blocks: List[int], split: int) -> int:\n",
    "        heapq.heapify(blocks) \n",
    "        while len(blocks) > 1:\n",
    "            a, b = heapq.heappop(blocks), heapq.heappop(blocks)\n",
    "            c = max(a, b) + split \n",
    "            heapq.heappush(blocks, c) \n",
    "        return blocks[0] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBuildTime(self, blocks: List[int], split: int) -> int:\n",
    "        pqu=[]  #小根堆\n",
    "        n=len(blocks)\n",
    "        if n==1:return blocks[0]\n",
    "        for i in range(0,n):\n",
    "            heapq.heappush(pqu,blocks[i])\n",
    "        while len(pqu)>1:\n",
    "            x=heapq.heappop(pqu)\n",
    "            y=heapq.heappop(pqu)\n",
    "            heapq.heappush(pqu,split+max(x,y))\n",
    "        return pqu[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq\n",
    "class Solution:\n",
    "    def minBuildTime(self, blocks: List[int], split: int) -> int:\n",
    "        heap=[]\n",
    "        for x in blocks:\n",
    "            hq.heappush(heap,x)\n",
    "\n",
    "        while len(heap)>1:\n",
    "            a=hq.heappop(heap)\n",
    "            b=hq.heappop(heap)\n",
    "            t=split+max(a,b)\n",
    "            hq.heappush(heap,t)\n",
    "        \n",
    "        return heap[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBuildTime(self, blocks: List[int], split: int) -> int:\n",
    "        # 哈夫曼树\n",
    "        q = blocks.copy()\n",
    "        heapq.heapify(q)\n",
    "        while len(q) > 1:\n",
    "            heapq.heappush(q, max(heappop(q), heappop(q)) + split)\n",
    "        return q[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBuildTime(self, pq: List[int], split: int) -> int:\n",
    "        heapify(pq)\n",
    "        while len(pq) > 1:\n",
    "            heappop(pq)\n",
    "            heappushpop(pq, pq[0] + split)\n",
    "        return pq[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "class Solution:\n",
    "    def minBuildTime(self, blocks: List[int], split: int) -> int:\n",
    "        lst = []\n",
    "        for block in blocks:\n",
    "            heappush(lst, block)\n",
    "        while len(lst) > 1:\n",
    "            a = heappop(lst)\n",
    "            b = heappop(lst)\n",
    "            heappush(lst, split + max(a, b))\n",
    "        return lst[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBuildTime(self, blocks: List[int], split: int) -> int:\n",
    "        h = []\n",
    "        for x in blocks:\n",
    "            heapq.heappush(h, x)\n",
    "        \n",
    "        while len(h) > 1:\n",
    "            a = heapq.heappop(h)\n",
    "            b = heapq.heappop(h)\n",
    "            new_node = max(a, b) + split\n",
    "            heapq.heappush(h, new_node)\n",
    "        return h[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBuildTime(self, blocks: List[int], split: int) -> int:\n",
    "        blocks.sort(reverse=True)\n",
    "        def judge(x):\n",
    "            if x < blocks[0]:\n",
    "                return False\n",
    "            cnt = 1\n",
    "            for r in range(len(blocks)):\n",
    "                t = (x - blocks[r]) // split\n",
    "                x -= t * split\n",
    "                cnt *= 2 ** t\n",
    "                cnt -= 1\n",
    "                if cnt < 0:\n",
    "                    return False\n",
    "            return True\n",
    "        l, r = 0, 10 ** 8\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if judge(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
